Error correcting codes allow the detection and the correction of errors caused by channel noise, interference or any impairment affecting data during its storage or transmission from a transmitter to a receiver. The detection and/or correction of errors rely on the addition of redundant data to the original data during the encoding process.
Error correcting codes are used in numerous data transfer and storage systems and devices to provide a reliable and possibly error-free delivery of digital data over noisy unreliable transmission channels. Such techniques are facing significant demand and are used in various applications including voice and multimedia transmission for example in wireless ad-hoc networks (e.g. standardized in Wi-Fi 802.11), in radio communication systems (e.g. in 3G, 4G/LTE, 5G and beyond), in optical fiber-based transmission systems, and in digital video broadcasting (e.g. standardized in DVB-C2, DVB-S2X, and DVB-T2).
Linear codes belong to the class of error correcting codes. They are characterized by the linearity property of the codewords, according to which any linear combination of two or more codewords is a codeword.
According to a first linear ‘convolutional coding’ approach using convolutional codes, the encoding process is based on encoding data symbol-by-symbol.
According to a second linear ‘block coding’ approach, the encoding process is based on encoding data by blocks of symbols of a fixed size. Exemplary linear block codes comprise the Hamming codes, the Reed-Solomon codes, the Turbo codes and the low-density parity-check (LDPC) codes.
Error correcting codes may be binary or non-binary. Codes constructed over Galois Fields GF(q) of order q=2 are binary codes. Accordingly, the various components of any codeword (hereinafter referred to as ‘symbols’) belong to the set of values {0,1}. Codes constructed over Galois Fields GF(q) of order q>2 are non-binary. Accordingly, the various symbols take values in GF(q).
Given the linearity property, any linear error correcting code can be represented by a generator matrix, generally denoted by G, and a parity-check matrix, generally denoted by H, linked by the relation G. Ht=0. Entries of the generator and parity-check matrices belong to the Field over which the code is constructed. The parity-check matrix defines the parity-check constraints designed to be satisfied by the codewords. In particular, LDPC codes are specified by sparse parity-check matrices comprising a number of zero entries very much higher than the number of non-zero entries.
Decoding data encoded using linear error correcting codes can be performed based on a graph representation of the code, so-called ‘Tanner graph’, associated with the parity-check matrix of the underlying code. The graph representation of a linear error correcting code comprises two sets of nodes: a first set of nodes referred to as ‘variable nodes’ and a second set of nodes referred to as ‘check nodes’. Variable nodes and check nodes are linked together by edges. Variable nodes and check nodes form processing units. Each variable node is associated with a column of the parity-check matrix. Each check node is associated with a row of the parity-check matrix, i.e. with a parity-check equation. The connections between variable nodes and check nodes are determined by the non-zero entries of the parity-check matrix.
Iterative decoders can be used to decode data encoded using linear block error correcting codes. Given a noisy sequence of encoded symbols representing for example the output of a communication channel, an iterative decoder processes the noisy sequence during a number of iterations bringing it at each iteration closer to the original sequence of encoded symbols.
The Tanner graph representation can be used to implement iterative decoding. Accordingly, the decoding process can be performed by an iterative exchange of messages between the processing units associated with the variable nodes and check nodes via the different edges connecting them in the graph. Each variable node processing unit or check node processing unit receives input messages from the corresponding connected nodes in the graph and delivers, after processing the input messages, output messages to at least one processing unit corresponding to a connected node in the graph. The decoding process stops either if all parity-check constraints are satisfied, returning thus the decoded codeword, or by reaching a maximum number of iterations without meeting all parity check constraints.
Passed messages between the different variable node processing units and check node processing units carry information associated with the encoded symbols. A message may comprise a symbol and a metric measuring the reliability of the symbol (hereinafter referred to as ‘reliability metric’). The reliability metric of a symbol may correspond for example to its estimated probability density function, measuring the probability that this symbol is equal to each value in the Field of construction of the code which was used to encode.
Early iterative decoding algorithms were designed for binary codes and apply to binary LDPC codes. They are the ‘sum-product’ algorithm (also known as ‘belief propagation’ or ‘message passing’ algorithm) and the ‘min-sum’ algorithm disclosed both in “N. Wibereg, H-A. Loeliger, and R. Kotter, Codes and Iterative Decoding on General Graphs, European Transactions on Telecommunications and Related Technologies, special issue on Turbo Coding, June 1995”. They provide near-optimal performance in terms of error decoding probability.
Iterative decoding algorithms designed for non-binary codes were inspired by the ‘sum-product’ algorithm. Exemplary iterative decoders for non-binary codes comprise the ‘q-ary sum-product’ algorithm disclosed for example in:                “M. Davey and D. MacKay, Low-density parity check codes over GF(q), IEEE Communications Letters, vol. 2, no. 6, pages 165-167, June 1998”,        “D. J. C. Mackay and M. Davey, Evaluation of Gallager Codes for Short Block Length and High Rate Applications, In Proceedings of IMA Workshop on Codes, Systems and Graphical Models, 1999”, and        “L. Barnault and D. Declercq, Fast decoding algorithm for LDPC over GF(q), In Proceedings of IEEE Information Theory Workshop, pages 70-73, April 2003”.        
Some iterative decoding algorithms are based on logarithmic-scale computations for reducing the computational complexity by transforming product operations to simple summation operations. Such decoding schemes comprise:                the ‘max-log-map’ turbo codes decoder disclosed in “H. Sadjadpour, Maximum A Posteriori Decoding Algorithms For Turbo Codes, In Proceedings of SPIE, vol. 4045, 2000”,        the ‘extended min-sum’ (EMS) non-binary LDPC codes decoder disclosed in “D. Declercq and M. Fossorier, Decoding algorithms for non-binary LDPC codes over GF, IEEE Transactions on Communications, vol, 55, no. 4, pages 633-643, April 2007”, and        the ‘min-max’ non-binary LDPC codes decoder disclosed in “V. Savin, Min-max decoding for non-binary LDPC codes, In Proceedings of IEEE International Symposium on Information Theory, pages 960-964, July 2008”.        
The EMS algorithm is based on log-domain computations of the exchanged messages between the variable node processing units and the check node processing units. As the largest complexity of the EMS algorithm is the computation performed by the check node processing units, the EMS algorithm applies a sorting and truncation of processed messages to further alleviate the computational complexity and memory requirements at check node processing units. Message sorting is performed according to an order of the reliability metrics associated with the symbols comprised in the received input messages. Message truncation is performed for retaining the most reliable symbols in a given input and/or output message.
The computation of output messages at the level of the check node processing units from the sorted and truncated input messages can be performed according to various architectures. Existing architectures include “forward-backward” architectures and syndrome-based architectures.
In a “forward-backward” architecture, the computations performed by a check node processing unit are divided up into multiple serial calculations involving multiple elementary check node processing units (hereinafter referred to as ‘elementary check node processors’). Each elementary check node processor processes two or more input messages to generate an intermediary message that is subsequently used by remaining elementary check node processors, at later stages. Computed intermediary messages are sorted based on the reliability metrics associated with the decoded symbols. In addition, an elimination of redundancies is performed by each elementary check node processor to suppress messages comprising the same symbols while keeping the message comprising the most reliable of the redundant symbols. Exemplary algorithms for elementary check node processing comprise:                the ‘Bubble check’ algorithm disclosed in “E. Boutillon and L. Conde-Canencia, Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders, Electronics Letters, vol. 46, no. 9, pp. 633-634, April 2010”, and        an improved version of the ‘Bubble check’ algorithm known as ‘L-Bubble check’ disclosed “E. Boutillon, L. Conde-Canencia, and A. Al Ghouwayel, Design of a GF(64)-LDPC Decoder based on the EMS algorithm, IEEE Transactions on Circuits and Systems, vol. 60, no. 10, pages 2644-2656, October 2013”.        
The Bubble-check and L-Bubble check algorithms are based on a reduction of the search space of the best intermediary results computed by an elementary check node processor from two input messages.
In a syndrome-based architecture, a check node processing unit implements a syndrome-based decoding. The computation of output messages from the sorted and truncated input messages requires two steps. In a first step, the check node processing unit computes a set of values termed ‘syndromes’ involving all input messages. In a second step, a decorrelation operation is performed in association with each output message. The decorrelation operation consists in cancelling, from the computed syndromes, the contribution of the input message previously received from the variable node processing unit that is a recipient of the computed output message. The syndrome-based architecture is disclosed in:                “P. Schlafer, N. When, M. Alles, T. Lehnigk-Emden, and E. Boutillon, Syndrome based check node processing of high order NB-LDPC decoders, In Proceedings of the International Conference on Telecommunications, pages 156-162, April 2015”;        “P. Schlafer, et al., A new Architecture for High Speed, Low Latency NB-LDPC Check Node Processing, In Proceedings of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, August 2015”.        
A syndrome-based architecture allows parallel computation, which is particularly advantageous for higher-order Galois fields. However, with such an architecture, the computational complexity is dominated by the number of computed syndromes which increases as the number of the input messages increases.
The forward-backward architecture allows a reduction of the hardware cost. However, it introduces high latency resulting in degradation in the system throughput. The syndrome-based architecture introduces high complexity mainly due to the increasing number of computed syndromes. The implementations of the syndrome-based architecture in practical decoding systems require significant computational and storage resources that are not always available. In particular, some practical implementations of this architecture are not adapted to the decoding of non-binary codes having high coding rates.
There is accordingly a need for developing an efficient and low-complexity architecture for check node processing units implemented in an EMS decoder in particular, and in any Tanner graph-based iterative decoder in general.